НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Методи пошуку у масивах» Варіант № 15 Дата « 9 » червня 2022  Мета роботи: Метою лабораторної роботи є отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методі Теоретичні відомості: Пошук методом бар’єром Перевагою методу простого пошуку  є його простота та наочність. Недоліком методу є те, що у заголовку циклу доводиться здійснювати дві перевірки: на допустимість індексу і на рівність значення. Якби ми знали, що шукане значення точно є десь у масиві, то першу перевірку можна було б не вказувати, що прискорило б пошук. Це наштовхує на думку, у вихідний масив потрібно тимчасово  включити шукане значення. Однак, оскільки розміри масиву змінені бути не можуть, включення можна здійснити на останнє місце масиву. Тоді  після завершення  пошуку потрібно повернути в кінець масиву початкове значення.  Для одержання  результату пошуку потрібно перевірити , чи дорівнює шукане значення тому елементові масиву, на якому відбулось завершення роботи алгоритму. Навіть, якщо елемент у початковому масиві був відсутній, і зупинка була здійснена на включеному в масив зразкові, перевірка результату буде проведена для вихідного елементу масиву, який на той час замінить зразок пошуку. Наведений метод  називається “пошук елементу з бар'єром”. Роль бар’єрного елементу виконує включений в масив зразок пошуку. Включення повинно здійснюватись тільки замість останнього елементу масиву, після якого інших елементів немає. Пошук послідовності елементів масиву Одне з найпростіших завдань пошуку інформації – пошук точно заданого підрядка у рядку. Проте, це завдання надзвичайно важливе – воно застосовується в текстових редакторах, СУБД, пошукових машинах тощо. Пошук рядка формально визначається в такий спосіб. Нехай заданий масив Т з N елементами і масив W з M елементами, причому 0 < M ≤ N. Пошук рядка виявляє перше входження W у Т, результатом будемо вважати індекс і, що вказує на перший з початку рядка (з початку масиву Т) збіг зі зразком (словом). Алгоритм Рабіна-Карпа Алгоритм Рабіна-Карпа – це алгоритм пошуку рядка, який шукає шаблон, тобто підрядок, у тексті використовуючи хешування. Ідея алгоритму: Є рядок A, довжина якого дорівнює m, потрібно знайти зразок X довжиною n. Виріжемо "віконечко" розміром n і перевіряємо по вхідному рядку. Шукаємо слово в "віконечку" із заданим зразком. Порівнювати по буквах довго. Замість цього фіксуємо деяку числову функцію на словах довжиною n, тоді завдання зведеться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" і на зразку різні, то збігу немає. Тільки якщо значення однакові, необхідно перевіряти послідовно збіг по буквах Завдання для виконання: 1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром. 2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом: / Результат виконання роботи: Пошук бар’єром: Розмір матриці Час виконання  10х10 4542 мс  50х50 21047 мс  100х100 48426 мс   Пошук послідовності елементів в масиві: Розмір матриці Час виконання  10х10 3399 мс  50х50 11271 мс  100х100 22968 мс   // Висновок: Під час виконання даної лабораторної роботи було набуто практичних навичок в обробці масивів, а саме, виконано пошук елементів у матриці зі допомогою методу з бар’єром, та пошук послідовності елементів у масиві. Часова характеристика даних алгоритмів наведена у таблицях вище. Виконані алгоритми працюють згідно вимог. Посилання на Replit: https://replit.com/join/jvwwqczymu-tr-15fundamient Копія коду: #include <iostream> #inclu...